package Day2025_04_25;

/**
 * 题目: 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的 回文 子串。
 */


/**
 * 这里面难点就是怎么判断是否为回文串
 * 判断是否为回文串有两种方法 : 所以衍生出两种处理方法
 * 1. 直接遍历判断 此方法时间复杂度较大
 * 时间复杂度 O(n^2)  空间复杂度 O(n)
 *
 * 2. 中心扩展法, 选取一个中心字符, 向两边扩展 (这里注意细节, 可能是从一个字符开始扩展,
 * 也有可能是从两个字符开始扩展, 要分类讨论) 此方法时间复杂度最小
 * 时间复杂度 O(n * k) (k 为最长回文串的长度)  空间复杂度 O(1)
 *
 *
 * 3. 还有一种方法, 就是动态规划
 * 时间复杂度 O(n^2) 空间复杂度 O(n^2)
 */


public class LeetCode5 {
    // 方法一: 直接暴力
    public String longestPalindrome(String s) {
        int n = s.length();
        char[] ss = s.toCharArray();

        // start记录最长回文串的起始位置, len记录最长回文串的长度
        int start = 0, len = 0;

        // 两层 for循环遍历所有组合
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {

                // 如果是回文串开始记录, 否则进入下次循环
                if (isPalindRome(ss, i, j)) {

                    // 判断此回文串的长度是否大于之前的最大长度
                    if (j - i + 1 > len) {

                        // 如果大于更新起始位置, 和最大长度
                        len = j - i + 1;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, start + len);
    }

    // 暴力解决是否为回文串的问题
    private boolean isPalindRome(char[] ss, int left, int right) {
        while (left < right) {
            // 如果最外面的字母相同, 判断里面的,
            // 不相同直接就不是回文串了
            if (ss[left] == ss[right]) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }

    // *****************************************************************
    // 方法二: 中心扩展法
    public String longestPalindrome2(String s) {
        int n = s.length();
        char[] ss = s.toCharArray();

        // start记录最长回文串的起始位置, len记录最长回文串的长度
        int start = 0, len = 0;

        // 选取一个中心字符
        for (int i = 0; i < n; i++) {

            // 从一个字符开始
            int left = i, right = i;

            // 给越界情况
            while (left >= 0 && right < n) {

                // 如果两边字符不相等, 直接退出循环
                // 否则继续向两边扩展 (left--, right++)
                if (ss[left] != ss[right]) {
                    break;
                } else {
                    left--;
                    right++;
                }
            }

            // 记录更新情况
            // 注意: 因为这种方法在判断上有一个延迟, 所以 left和 right都会比平常有一各单位的偏移量
            // 我们需要主义好下标的映射问题
            if (right - left - 1 > len) {
                len = right - left - 1;
                start = left + 1;
            }

            // 转到以两个字符为中心
            left = i;
            right = i + 1;

            while (left >= 0 && right < n) {
                if (ss[left] != ss[right]) {
                    break;
                } else {
                    left--;
                    right++;
                }
            }
            if (right - left - 1 > len) {
                len = right - left - 1;
                start = left + 1;
            }
        }
        return s.substring(start, start + len);
    }

    // ************************************************************
    // 方法三: 动态规划
    public String longestPalindrome3(String s) {
        int n = s.length();
        char[] ss = s.toCharArray();

        // start记录最长回文串的起始位置, len记录最长回文串的长度
        int start = 0, len = 0;

        // 状态表示 dp[i][j] : 字符串 s的 i, j位置下的子串是否为回文串
        // 定义转态转移方程:
        boolean[][] dp = new boolean[n][n];

        // 因为填写 dp表需要 i + 1的数据, 所以 i的方向要从后向前
        for (int i = n - 1; i >= 0; i--) {

            // j需要 j - 1的数据, 所以从前向后
            for (int j = i; j < n; j++) {

                // 如果两个字符相同, 现在要想三种情况
                // 1. i == j 直接返回 true
                // 2. i + 1 == j 返回true
                // 3. i + 1 < j 需要的是前面的状态
                // 还可以避免越界情况
                if (ss[i] == ss[j]) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }

                // 如果此子串是回文串且长度大于之前记录的长度, 更新长度和起始位置
                if (dp[i][j] && j - i + 1 > len) {
                    len = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substring(start, start + len);
    }
}
